package com.hqq.search.symbol_table;

import com.hqq.search.KeyMap;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * SequentialListSymbolTableSearch
 * 基于无序链表的符号表实现
 * Created by heqianqian on 2017/8/5.
 */
public class SequentialListSymbolTableSearch<K, V> implements KeyMap<K, V> {

    private Node first;

    private int count = 0;

    private List<K> keyList;

    private List<V> valueList;

    public SequentialListSymbolTableSearch() {
        first = new Node(null, null, null);
        keyList = new ArrayList<>();
        valueList = new ArrayList<>();
    }

    @Override
    public void put(K key, V value) {
        first.put(key, value);
        keyList.add(key);
        valueList.add(value);
        count++;
    }

    @Override
    public V get(K key) {
        return first.get(key);
    }

    @Override
    public void delete(K key) {
        Node node1 = first.next;
        Node node2 = first;
        while (node1 != null) {
            if (node1.key.equals(key)) {
                System.out.println("找到删除元素");
                break;
            } else {
                node2 = node1;
                node1 = node1.next;
            }
        }
        node2.next = node1.next;
        node1.next = null;
    }

    @Override
    public int size() {
        return count;
    }

    public List<K> keySet() {
        return this.keyList;
    }

    @Override
    public Iterator<K> iterator() {
        return new ListSTSearchIterator(this);
    }

    /**
     * 链表型数组迭代器
     */
    private class ListSTSearchIterator implements Iterator<K> {

        private SequentialListSymbolTableSearch<K, V> table;

        private int index = 0;

        public ListSTSearchIterator(SequentialListSymbolTableSearch<K, V> table) {
            this.table = table;
        }

        @Override
        public boolean hasNext() {
            return index != count;
        }

        @Override
        public K next() {
            return table.keySet().get(index++);
        }
    }

    /**
     * 链表节点
     */
    private class Node {
        private K key;
        private V value;
        private Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public V get(K key) {
            for (Node node = first; node != null; node = node.next) {
                if (node.key == key) {
                    return node.value;
                }
            }
            return value;
        }

        public void put(K key, V value) {
            boolean exists = false;
            for (Node node = first; node != null; node = node.next) {
                if (node.key == key) {
                    node.value = value;
                    exists = true;
                }
            }
            if (!exists) {
                first = new Node(key, value, first);
            }
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key.toString() +
                    ", value=" + value.toString() +
                    '}';
        }
    }

}
